package com.awei.study.dataStructure.link;

import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * 去除链表中的元素
 */
public class inkList_element_demo extends LinkList_Abs {

    /**
     * 去除倒数第几个元素 递归
     */
    @Test
    public void test1() {
        LinkNode l1 = prepareData();
        print(l1);
        LinkNode s = new LinkNode(-1, l1);
        bfsLinkList(s, 1);
        print(s);
    }

    public int bfsLinkList(LinkNode p, int remove) {
        if (p == null) return 0;
        int next = bfsLinkList(p.next, remove);
        if (next == remove) {
            print(p);
            p.next = p.next.next;
        }
        return next + 1;
    }


    /**
     * 根据值删除链表元素    非递归
     */
    @Test
    public void test2() {
//        LinkNode l1 = prepareData();
        LinkNode l1 = prepareData("7,7,7,7");
        print(l1);
        LinkNode s = new LinkNode(-1, l1);
        int rem = 7;
        LinkNode p1 = s;
        LinkNode p2 = p1.next;
        while (p2 != null) {
            if (p2.value == rem) {
                p1.next = p2.next;
                p2 = p2.next;
            } else {
                p1 = p1.next;
                p2 = p2.next;
            }
        }
        print(s);
    }

    /**
     * 根据值删除链表元素    递归
     */
    @Test
    public void test3() {
        LinkNode l1 = prepareData();
//        LinkNode l1 = prepareData("7,7,7,7");
        print(l1);
        int rem = 3;
        LinkNode node = bfsLinkList1(l1, rem);
        print(node);
    }

    public LinkNode bfsLinkList1(LinkNode p, int rem) {
        if (p == null) return p;
        LinkNode node = bfsLinkList1(p.next, rem);
        if (p.value == rem) {
            return node;
        } else {
            p.next = node;
            return p;
        }
    }

    /**
     * 链表去重，连续元素只保留一个    非递归
     */
    @Test
    public void test4() {
//        LinkNode l1 = prepareData();
        LinkNode l1 = prepareData("1,2,2,3,3");
        print(l1);
        LinkNode p1 = l1;
        LinkNode p2 = p1.next;
        while (p2 != null) {
            if (p1.value == p2.value) {
                p1.next = p2.next;
                p2 = p2.next;
            } else {
                p1 = p1.next;
                p2 = p2.next;
            }
        }
        print(l1);
    }

    /**
     * 链表去重，连续元素只保留一个    递归
     */
    @Test
    public void test5() {
//        LinkNode l1 = prepareData();
        LinkNode l1 = prepareData("1,2,2,3,3");
        print(l1);
        LinkNode node = bfsLinkList2(l1);
        print(node);
    }

    public LinkNode bfsLinkList2(LinkNode p) {
        if (p == null || p.next == null) {
            return p;
        }
        if (p.value == p.next.value) {
            return bfsLinkList2(p.next);
        } else {
            p.next = bfsLinkList2(p.next);
            return p;
        }
    }

    /**
     * 合并连个有序列表    递归
     */
    @Test
    public void test6() {
//        LinkNode l1 = prepareData();
        LinkNode l1 = prepareData("1,3,5,8,9");
        LinkNode l2 = prepareData("2,4,6,7");
        print(l1);
        print(l2);
        LinkNode node = bfsLinkList3(l1, l2);
        print(node);
    }

    public LinkNode bfsLinkList3(LinkNode l1, LinkNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        if (l1.value < l2.value) {
            l1.next = bfsLinkList3(l1.next, l2);
            return l1;
        } else {
            l2.next = bfsLinkList3(l1, l2.next);
            return l2;
        }
    }

    /**
     * 合并连个有序列表    递归
     */
    @Test
    public void test7() {
        LinkNode l1 = prepareData("1,3,5,8,9");
        LinkNode l2 = prepareData("2,4,6,7");
        LinkNode l3 = prepareData("10,11,13,18");
        LinkNode l4 = prepareData("12,14,15,17");
        print(l1);
        print(l2);
        print(l3);
        print(l4);
        LinkNode[] arr = prepareDataArr(l1, l2, l3, l4);
        LinkNode node = bfsLinkList4(arr, 0, arr.length - 1);
        print(node);
    }

    public LinkNode bfsLinkList4(LinkNode[] arr, int l, int r) {
//        System.out.println("l = " + l + ", r = " + r);
        if (l == r) return arr[l];
        int m = (l + r) >>> 1;
        LinkNode left = bfsLinkList4(arr, l, m);
        LinkNode right = bfsLinkList4(arr, m + 1, r);
        return bfsLinkList3(left, right);
    }

    /**
     * 1 2 3 4 5 null
     * p1
     * p2
     *  p1
     *     p2
     *     p1  p2
     * 1 2 3 4 5 6 null
     * 返回中间元素
     */
    @Test
    public void test8() {
//        LinkNode l1 = prepareData("1,2,3,4,5");
        LinkNode l1 = prepareData("1,2,3,4,5,6");
        print(l1);
        LinkNode p1 = l1;
        LinkNode p2 = l1;
        while(p2 != null && p2.next != null) {
            p1 = p1.next;
            p2 = p2.next.next;
        }
        print(p1);
    }


    /**
     * 判断回文
     */
    @Test
    public void test9() {
        LinkNode l1 = prepareData("1,2,3,1,1");
        print(l1);
        LinkNode p1 = l1;
        LinkNode p2 = l1;
        while(p2 != null && p2.next != null) {
            p1 = p1.next;
            p2 = p2.next.next;
        }
        print(p1);

        LinkNode o1 = p1;
        LinkNode n1 = null;
        while(o1 != null) {
            LinkNode o2  = o1.next;
            o1.next = n1;
            n1 = o1;
            o1 = o2;
        }
        print(n1);

        while(n1 != null) {
            if(n1.value != l1.value) {
                System.out.println("false");
                break;
            }
            n1 = n1.next;
            l1 = l1.next;
        }
        System.out.println("true");
    }

    /**
     * 判断回文 基于test9 优化
     */
    @Test
    public void test10() {
        LinkNode l1 = prepareData("1,2,2,1");
        print(l1);
        LinkNode p1 = l1;
        LinkNode p2 = l1;
        LinkNode o1 = l1;
        LinkNode n1 = null;
        while(p2 != null && p2.next != null) {
            p1 = p1.next;
            p2 = p2.next.next;

            LinkNode o2 = o1.next;
            o1.next = n1;
            n1 = o1;
            o1 = o2;
        }
        print(p1);
        print(n1);
        if(p2 != null) {
            p1 = p1.next;
        }
        while(n1 != null) {
            if(p1.value != n1.value) {
                System.out.println(false);
                break;
            }
            p1 = p1.next;
            n1 = n1.next;
        }
        System.out.println("true");
    }

    /**
     * 判环
     */
    @Test
    public void test11() {
        LinkNode l1 = prepareCycle();
//        print(l1);
        LinkNode p1 = l1;
        LinkNode p2 = l1;
        while(p2 != null && p2.next != null) {
            p1 = p1.next;
            p2 = p2.next.next;
            if(p1 == p2) {
                System.out.println("true");
                break;
            }
        }
        System.out.println(false);
    }

    /**
     * 判断环的位置
     */
    @Test
    public void test12() {
        LinkNode l1 = prepareCycle();
//        print(l1);
        LinkNode p1 = l1;
        LinkNode p2 = l1;
        while(p2 != null && p2.next != null) {
            p1 = p1.next;
            p2 = p2.next.next;
            if(p1 == p2) {
                System.out.println("true");
                p1 = l1;
                while( true) {
                    if(p1 == p2) {
                        System.out.println(p1.value);
                        break;
                    }
                    p1 = p1.next;
                    p2 = p2.next;
                }
                break;
            }
        }
        System.out.println(false);
    }
}
